def test_1_wei_bag_problem(weight, value, bagWeight):
    # 初始化
    dp = [0] * (bagWeight + 1)
    for i in range(len(weight)):  # 遍历物品
        for j in range(bagWeight, weight[i] - 1, -1):  # 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

    return dp[bagWeight]


def error_test_1_wei_bag_problem(weight, value, bagWeight):
    # 初始化
    dp = [0] * (bagWeight + 1)
    """关于先遍历物品还是先遍历背包，可以这样记忆，先遍历物品(变量i)，这样遍历背包(变量j)时，才能得出 j in range(bagwight,weight[i]-1)
    """
    for j in range(bagWeight,0, -1):  # 遍历背包容量
        for i in range(len(weight)):  # 遍历物品
            if(j>=weight[i]):
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

    return dp[bagWeight]
#输出结果是30，说明确实当遍历顺序错误，一个背包中每次只能放一个物品

if __name__ == "__main__":

    weight = [1, 3, 4]
    value = [15, 20, 30]
    bagweight = 4
    result = error_test_1_wei_bag_problem(weight, value, bagweight)
    print(result)